package internal.exchange;

/**
 * @描述1：1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
 * @描述2：2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
 * @描述3：3）此时基准元素在其排好序后的正确位置
 * @描述4：4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
 * @效率：快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。
 * @适用场景：快速排序比大部分排序算法都要快。尽管在某些特殊的情况下有比快速排序快的算法，但通一般情况下，没有比它更快的。
 * @作者：hongxingfan
 * @时间：2014年9月5日 上午11:03:33
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] datas = { 9, 4, 1, 8, 7, 5, 2, 0, 3, 4, 6 };

        // 快速排序
        quickSort(datas, 0, datas.length - 1);

        // 输出
        for (int data : datas)
            System.out.print(data + " ");
        System.out.println();
    }

    // 递归，每次partition的位置就是正确的顺序位置
    public static void quickSort(int[] datas, int low, int high) {
        if (low < high) {
            int position = partition(datas, low, high);
            quickSort(datas, low, position - 1);
            quickSort(datas, position + 1, high);
        }
    }

    public static int partition(int[] datas, int low, int high) {
        int tmp = datas[low];
        while (low < high) {
            // high与low交换，不是tmp的交换；tmp的作用是比较
            while (low < high && datas[high] >= tmp)
                high--;
            // high跟low交换
            int tt = datas[high];
            datas[high] = datas[low];
            datas[low] = tt;

            while (low < high && datas[low] <= tmp)
                low++;
            tt = datas[low];
            datas[low] = datas[high];
            datas[high] = tt;
        }
        return low;
    }
}
